package com.ting.test.algorithms.递归和动态规划.从左往右的模型;


import java.util.ArrayList;

/**
 * 有一组咖啡机，每台制作咖啡的时间不同
 * 假设有一群人同时到达，如何让这群人排队，使得大家都能快速的喝上咖啡
 * 咖啡制作好后，人们一口气就喝完了，喝完一杯咖啡的时间忽略不计
 * <p>
 * 现在假设只有一个洗杯子的机器，一次只能洗一个杯子，洗一次个杯子需要耗时A
 * 而杯子也可以自己风干 需要耗时B
 * 求 所有的杯子都干净需要的耗时
 */
public class 咖啡机问题2 {
    public static void main(String[] args) {
        int[] arr = new int[]{1, 3, 7};//数组下标表示咖啡机编号，下标对应的值表示制作一杯咖啡需要的时间
        int[] drinks = new int[10];
        drinks = paidui(arr, drinks);

        int wash = 3;//洗一个杯子需要的耗时
        int dry = 10;//自然风干需要的耗时
        int index = 0;//表示从第index个杯子开始洗
        int cost = process(drinks, index, 0, wash, dry);
    }


    /**
     * @param drinks        每个人喝完咖啡的时间点
     * @param wash          洗一个杯子需要的耗时
     * @param dry           风干需要的耗时
     * @param index         当前需要洗的杯子
     * @param avaliableTime 咖啡机洗下一次可用的时间
     * @return 从第index个杯子开始，洗完所有的杯子需要的耗时
     */
    private static int process(int[] drinks, int index, int avaliableTime, int wash, int dry) {
        //base case
        if (index == drinks.length) {
            //index最大值是drinks.length-1
            // 因此当idnex=drinks.length 表示杯子已经洗完了
            return 0;
        }
        //index < drinks.length
        // 考虑第一种情况,当前的杯子用机器洗，那么洗完当前杯子，以及之后的所有杯子的需要多长时间
        //首先求出，当前杯子最早在什么时间点可以开始洗
        //因为要使用机器，如果当前人喝完了，但是机器还不能用（还在洗上一个杯子）,那么实际上也是不能开始洗的
        //同样，如果当前机器可以用了，但是当前杯子还没被喝完，也是不能洗
        //因此，这里求的二者的最大值作为当前杯子真正开始洗的时间
        int currentCleanTime1 = Math.max(avaliableTime, drinks[index]) + wash;////求出使用机器洗当前杯子在什么时间点可以洗完
        int restCleanTime1 = process(drinks, index + 1, currentCleanTime1, wash, dry);//求出剩下的所有杯子在什么时间点洗完

        //注意 在第一种情况下，最终的耗时是restCleanTime1和currentCleanTime1的最大值
        //因为，当前杯子用机器洗，下一个杯子可能是自然挥发的，比如说，机器洗一次需要100万年，而自然挥发需要10秒钟
        //那么如果当前杯子选择机器洗，后续的杯子肯定都选择自然挥发，而这种方案最大的耗时自然是机器洗的
        // 因此要取他们的最大值，
        // 而且我们目的是要比较两种方案，哪一种最优
        //因此首先要找出每种方案的最大值，在最大值中选取一个最小的就是最优方案
        int cost1 = Math.max(restCleanTime1, currentCleanTime1);

        // 第二种情况,当前杯子选择自然风干
        //那么当前杯子在喝完后就可以立即开始了
        //由于没有使用机器，那么机器下一次可用时间还是当前的时间
        int currentCleanTime2 = drinks[index] + dry;//当前杯子挥发需要的时间
        int restCleanTime2 = process(drinks, index + 1, avaliableTime, wash, dry);//后续杯子洗干净需要的时间
        //当前杯子挥发，和后续杯子洗是并行的，因此取他们的最大值
        int cost2 = Math.max(currentCleanTime2, restCleanTime2);
        // 我们目的是要比较两种方案，哪一种最优
        //因此首先要找出每种方案的最大值，在最大值中选取一个最小的就是最优方案
        return Math.min(cost2, cost1);
    }

    /**
     * @param arr    咖啡机
     * @param drinks 排队的人
     * @return 每个排队的人喝完咖啡的时间点
     */
    private static int[] paidui(int[] arr, int[] drinks) {
        SmallHeap smallHeap = new SmallHeap(arr);
        for (int index = 0; index < drinks.length; index++) {
            Elements elements = smallHeap.pop();
            arr[index] = elements.start + elements.cost;
        }
        return arr;
    }


    static class SmallHeap {
        ArrayList<Elements> heap = new ArrayList();
        int size = 0;

        public SmallHeap(int[] arr) {
            for (int cost : arr) {
                heapInsert(0, cost);
            }
        }

        public void heapInsert(int startTime, int cost) {
            heap.add(new Elements(startTime, cost));
            int index = size;
            size++;
            int parent = index / 2;
            while (parent >= 0) {
                if (compare(parent, index)) {
                    swap(parent, index);
                }
                index = parent;
                parent = index / 2;
            }
        }

        private void swap(int parent, int index) {
            Elements elements = heap.get(parent);
            heap.set(parent, heap.get(index));
            heap.set(index, elements);
        }

        private boolean compare(int left, int right) {
            return (heap.get(left).start + heap.get(left).cost) > (heap.get(right).start + heap.get(right).cost);
        }

        public Elements pop() {
            Elements elements = heap.get(0);
            swap(0, size - 1);
            heap.remove(size);
            size--;
            return elements;
        }
    }


    static class Elements {
        int start;//咖啡机可以使用的时间点
        int cost;//制作一杯开发需要的耗时

        public Elements(int start, int cost) {
            this.start = start;
            this.cost = cost;
        }

        public int getStart() {
            return start;
        }

        public void setStart(int start) {
            this.start = start;
        }

        public int getCost() {
            return cost;
        }

        public void setCost(int cost) {
            this.cost = cost;
        }
    }
}
